﻿using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;

namespace Yuchen.NPA.Core.CompilerService.RegularExpression
{
    public class RegexParser
    {
        private readonly TextReader _textReader;
        private readonly StringBuilder sb = new StringBuilder();

        public RegexParser(string expression)
        {
            _textReader = new StringReader(expression);
        }

        private Node Expression()
        {
            var termNode = Term();
            var nextC = _textReader.Peek();
            if (nextC == -1)
            {
                return termNode;
            }

            var unionNode = termNode;
            var nextChar = (char)nextC;
            while (nextChar == '|')
            {
                _textReader.Read();
                sb.Append(nextChar);
                unionNode = new UnionNode(unionNode, Term());
                nextC = _textReader.Peek();
                if (nextC == -1)
                {
                    break;
                }

                nextChar = (char)nextC;
            }

            return unionNode;
        }

        private Node GetTerm()
        {
            var node = Factor();
            if (node == null)
            {
                return null;
            }
            var nextC = _textReader.Peek();
            if (nextC == -1)
            {
                return node;
            }
            var nextChar = (char)nextC;
            if (nextChar == '*')
            {
                _textReader.Read();
                sb.Append(nextChar);
                node = new StarNode(node);
            }

            return node;
        }

        private Node Term()
        {
            var node = GetTerm();
            while (true)
            {
                var nextNode = GetTerm();
                if (nextNode == null)
                {
                    return node;
                }
                node = new ConcatNode(node, nextNode);
            }
        }

        private List<Node> Selection()
        {
            var factorNode = Factor();
            if (factorNode == null)
            {
                return null;
            }

            var nodes = new List<Node>
            {
                factorNode
            };
            var nextC = _textReader.Peek();
            if (nextC == -1)
            {
                return nodes;
            }

            var nextChar = (char)nextC;
            if (nextChar == '-')
            {
                _textReader.Read();
                sb.Append(nextChar);
                //a-z
                //A-Z
                //0-9
                nextC = _textReader.Peek();
                if (nextC == -1)
                {
                    throw new Exception("分析错误");
                }

                nextChar = (char)nextC;
                var firstChar = ((CharNode)factorNode).Char;
                if (char.IsLetter(firstChar) && char.IsLetter(nextChar))
                {
                    if (!((char.IsLower(firstChar) && char.IsLower(nextChar))
                        || (char.IsUpper(firstChar) && char.IsUpper(nextChar))))
                    {
                        throw new Exception("分析错误");
                    }
                }
                else if (!(char.IsNumber(firstChar) && char.IsNumber(nextChar)))
                {
                    throw new Exception("分析错误");
                }
                _textReader.Read();
                sb.Append(nextChar);

                var start = firstChar + 1;
                var end = (int)nextChar;
                nodes.AddRange(Enumerable.Range(start, end - start + 1).Select(x => new CharNode((char)x)));
                return nodes;
            }
            var invalidChars = @"[]()*";
            while (!invalidChars.Contains(nextChar))
            {
                nodes.Add(Factor());
                nextC = _textReader.Peek();
                if (nextC == -1)
                {
                    break;
                }

                nextChar = (char)nextC;
            }

            return nodes;
        }

        public State ToDFA()
        {
            var state = ToNFA();
            var epsStates = EPSClosure(state, new HashSet<State>());
            var map = new Dictionary<ISet<State>, State>();
            var queue = new Queue<ISet<State>>();
            var workList = new Queue<ISet<State>>();
            queue.Enqueue(epsStates);
            workList.Enqueue(epsStates);
            while (workList.Any())
            {
                var states = workList.Dequeue();
                var startState = map.FirstOrDefault(x => x.Key.All(states.Contains) && x.Key.Count == states.Count).Value;
                if (startState == null)
                {
                    startState = new State();
                    startState.IsAccepted = states.Any(x => x.IsAccepted);
                    startState.IsStart = states.Any(x => x.IsStart);
                    map.Add(states, startState);
                }
                var chars = states.SelectMany(y => y.NextStates.Where(x => x.Key.InputCharacter != null)
                        .Select(x => x.Key.InputCharacter.Value))
                        .Distinct()
                        .ToList();
                foreach (var c in chars)
                {
                    var nextEpsStates = new HashSet<State>(states.SelectMany(y =>
                    {
                        var nextStates = y.NextStates.Where(x => x.Key.InputCharacter == c);
                        epsStates = new HashSet<State>();
                        foreach (var nextState in nextStates)
                        {
                            foreach (var state1 in EPSClosure(nextState.Value, new HashSet<State>()))
                            {
                                epsStates.Add(state1);
                            }
                        }

                        return epsStates;
                    }));
                    var newState = map.FirstOrDefault(x => x.Key.All(nextEpsStates.Contains) && x.Key.Count == nextEpsStates.Count).Value;
                    if (newState == null)
                    {
                        newState = new State();
                        newState.IsAccepted = nextEpsStates.Any(x => x.IsAccepted);
                        newState.IsStart = false;
                        map.Add(nextEpsStates, newState);
                    }
                    startState.AddNextState(c, newState);
                    if (queue.Any(x => x.Count == nextEpsStates.Count && x.All(nextEpsStates.Contains)))
                    {
                        continue;
                    }
                    queue.Enqueue(nextEpsStates);
                    workList.Enqueue(nextEpsStates);
                }
            }

            return map.FirstOrDefault().Value;
        }

        void FillNextStates(State key, Dictionary<State, IEnumerable<State>> allStatesMap)
        {
            key.NextStates.Clear();
            var states = allStatesMap[key];
            var chars = states.SelectMany(x => x.NextStates.Keys).Select(x => x.InputCharacter).ToList();
            foreach (var c in chars)
            {
                var nextStates = states.SelectMany(x => x.NextStates.Where(e => e.Key.InputCharacter == c).Select(y => y.Value)).ToList();
                var nextStateKeys = nextStates.Select(x => allStatesMap.FirstOrDefault(y => y.Value.Contains(x)).Key).Distinct().ToList();
                nextStateKeys.ForEach(p =>
                {
                    var edge = key.NextStates.Keys.FirstOrDefault(x => x.InputCharacter == c);
                    if (edge != null && key.NextStates[edge] == p)
                    {
                        return;
                    }
                    key.AddNextState(c, p);
                });
            }
        }

        public State ToMinimizeDFA()
        {
            var dfa = ToDFA();
            var allStates = dfa.States;
            var acceptStates = allStates.Where(x => x.IsAccepted).ToList();
            var notAcceptStates = allStates.Where(x => !x.IsAccepted).ToList();
            var allStatesMap = new Dictionary<State, IEnumerable<State>>();
            allStatesMap.Add(new State()
            {
                IsStart = notAcceptStates.Any(x => x.IsStart),
                IsAccepted = notAcceptStates.Any(x => x.IsAccepted)
            }, notAcceptStates);
            allStatesMap.Add(new State()
            {
                IsAccepted = acceptStates.Any(x => x.IsAccepted),
                IsStart = acceptStates.Any(x => x.IsStart)
            }, acceptStates);
            var stateKeyToStatesMap = new Dictionary<State, State>();
            foreach (var stateKey in allStatesMap.Keys)
            {
                var states = allStatesMap[stateKey];
                foreach (var state in states)
                {
                    stateKeyToStatesMap.Add(state, stateKey);
                }
            }
            var changed = true;
            var toRemoveKey = new HashSet<State>();
            var toAddMap = new Dictionary<State, IEnumerable<State>>();
            while (changed)
            {
                changed = false;
                foreach (var key in allStatesMap.Keys)
                {
                    FillNextStates(key, allStatesMap);
                }
                stateKeyToStatesMap.Clear();
                foreach (var stateKey in allStatesMap.Keys)
                {
                    var states = allStatesMap[stateKey];
                    foreach (var state in states)
                    {
                        stateKeyToStatesMap.Add(state, stateKey);
                    }
                }
                foreach (var stateKey in allStatesMap.Keys)
                {
                    if (toRemoveKey.Contains(stateKey))
                    {
                        continue;
                    }
                    var currentStates = allStatesMap[stateKey];
                    if (currentStates.Count() <= 1)
                    {
                        continue;
                    }
                    var chars = currentStates.SelectMany(x => x.NextStates.Select(y => y.Key.InputCharacter.Value)).ToList();
                    foreach (var c in chars)
                    {
                        var nextStatesGroups = currentStates.Select(x => new
                        {
                            Next = x.NextStates.FirstOrDefault(y => y.Key.InputCharacter == c).Value,
                            Current = x
                        }).Select(x => new
                        {
                            NextKey = x.Next == null ?
                                null :
                                stateKeyToStatesMap[x.Next],
                            x.Current
                        }).GroupBy(x => x.NextKey).ToList();

                        if (nextStatesGroups.Count() <= 1)
                        {
                            continue;
                        }

                        changed = true;
                        toRemoveKey.Add(stateKey);
                        foreach (var nextStateCollectionGroup in nextStatesGroups)
                        {
                            var newState = new State();
                            var currentGroupStates = nextStateCollectionGroup.Select(x => x.Current).ToList();
                            newState.IsAccepted = currentGroupStates.Any(x => x.IsAccepted);
                            newState.IsStart = currentGroupStates.Any(x => x.IsStart);
                            toAddMap.Add(newState, currentGroupStates);
                        }
                        break;
                    }

                    if (changed)
                    {
                        break;
                    }
                }

                foreach (var state in toRemoveKey)
                {
                    allStatesMap.Remove(state);
                }
                toRemoveKey.Clear();
                foreach (var kv in toAddMap)
                {
                    allStatesMap.Add(kv.Key, kv.Value);
                }
                toAddMap.Clear();
            }

            return allStatesMap.FirstOrDefault(x => x.Key.IsStart).Key;
        }

        private ISet<State> EPSClosure(State state, ISet<State> visited)
        {
            visited.Add(state);
            var list = new HashSet<State>();
            list.Add(state);
            var nextStates = state.NextStates.Where(x => x.Key.InputCharacter == null);
            foreach (var keyValuePair in nextStates)
            {
                if (visited.Contains(keyValuePair.Value))
                {
                    continue;
                }

                var states = EPSClosure(keyValuePair.Value, visited);
                foreach (var state1 in states)
                {
                    list.Add(state1);
                }
            }

            return list;
        }

        private Node Factor()
        {
            var c = _textReader.Peek();
            if (c == -1)
            {
                return null;
            }

            Node node = null;
            var nodeChar = (char)c;
            var nextChar = ' ';
            if (nodeChar == '|' || nodeChar == ')' || nodeChar == ']' || nodeChar == '*')
            {
                return null;
            }

            _textReader.Read();
            sb.Append(nodeChar);
            switch (nodeChar)
            {
                case '\\':
                    nextChar = (char)_textReader.Read();
                    sb.Append(nextChar);
                    if (!new char[] { '$', '^', '\\', 'w', 's', 'd', '[', ']', '*', '(', ')', '-', '|' }.Contains(nextChar))
                    {
                        throw new Exception(@"应该是$^\wsd[]*()-|，实际是" + nextChar.ToString());
                    }

                    node = new EscapeNode(nextChar);
                    break;
                case '(':
                    node = new GroupNode(Expression());
                    c = _textReader.Read();
                    if (c == -1)
                    {
                        throw new Exception("应该是),实际已经到结尾");
                    }
                    nextChar = (char)c;
                    if (nextChar != ')')
                    {
                        throw new Exception("应该是),实际是" + nextChar);
                    }
                    sb.Append(nextChar);
                    break;
                case '[':
                    node = new SelectionNode(Selection().ToArray());
                    c = _textReader.Read();
                    if (c == -1)
                    {
                        throw new Exception("应该是],实际已经到结尾");
                    }
                    nextChar = (char)c;
                    if (nextChar != ']')
                    {
                        throw new Exception("应该是],实际是" + nextChar);
                    }
                    sb.Append(nextChar);
                    break;
                default:
                    node = new CharNode(nodeChar);
                    break;
            }

            return node;
        }

        public State ToNFA()
        {
            var expression = Expression();
            var visitor = new NFAExpressionVisitor();
            expression.Accept(visitor);
            return visitor.State;
        }
    }
}
